package com.leetcode.algorithm.二叉树;

import java.io.*;

public class lc104二叉树的最大深度 {
    private static String line;
    private static String[] parts;
    private static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while((line=in.readLine())!=null){
            parts=line.split(" ");
            n= parts.length;
            String[] levelOrder=new String[n];
            for (int i = 0; i < n; i++) {
                levelOrder[i]=parts[i];
            }
            TreeNode root=createTree(levelOrder);
            out.println(maxDepth(root));
            out.flush();
        }
        out.close();
    }

    private static int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }else{
            int left=maxDepth(root.left);
            int right=maxDepth(root.right);
            return Math.max(left,right)+1;
        }
    }

    private static TreeNode createTree(String[] levelOrder) {
        if (levelOrder.length==0||levelOrder[0].equals("null")) return null;
        TreeNode[] nodes=new TreeNode[n];
        for (int i = 0; i < n; i++) {
            if (!levelOrder[i].equals("null")){
                nodes[i]=new TreeNode(Integer.parseInt(levelOrder[i]));
            }else {
                nodes[i]=null;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nodes[i]!=null){
                int leftIndex=i*2+1;
                int rightIndex=i*2+2;
                if(leftIndex<n) nodes[i].left=nodes[leftIndex];
                if (rightIndex<n) nodes[i].right=nodes[rightIndex];
            }
        }
        return nodes[0];
    }
}
